package sort;

public class HeapSort {
    public void sort(int[] nums) {
        int len = nums.length;
        buildMaxHeap(nums);
        for (int i = len - 1; i > 0; i--) {
            swap(nums, 0, i);
            headpify(nums, 0, i);
        }
    }

    private void buildMaxHeap(int[] nums) {
        // 这里 len / 2 后半部分的节点都是没有子节点的，所以构建只需要从前半部分开始就行了
        for (int i = nums.length / 2; i >= 0; i--) {
            headpify(nums, i, nums.length);
        }
    }

    private void headpify(int[] nums, int current, int len) {
        int left = 2 * current + 1, right = 2 * current + 2;
        int maxIdx = current;
        if (left < len && nums[left] > nums[maxIdx])
            maxIdx = left;
        if (right < len && nums[right] > nums[maxIdx])
            maxIdx = right;
        if (maxIdx != current) {
            swap(nums, maxIdx, current);
            headpify(nums, maxIdx, len);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
